import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.TreeNode;
import java.util.TreeMap;

public class Test {
    public int size(TreeNode root){
        if(root ==null){
            return 0;
        }
        Size ++;
        //计算二叉树中节点的个数
        size(root.left)
        size(root.right);

        return Size;


    }
    public int size2(TreeNode root){
        //树的节点由左子树+右子树+1
        //需要用到返回值
        if(root ==null){
            return 0 ;
        }
        //什么是递归的思想？并不是一杆子到底，只是大事化小，小事化了的思想
        int size = size(root.left)+size(root.right)+1;

        return size;

    }

    //题3 获取树中叶子节点的个数
  public void Size(TreeNode   root ){
        if(root ==null){
            return ;
        }


      if(root.left ==null&&root.right ==null){
          //说明此节点是叶子节点
          Count++;
      }
        Size(root.left);
        Size(root.right);


  }
    public int Size2(TreeNode root){
        //整棵树的叶子节点等于左子树的节点+右子树的叶子节点
        if(root ==null){
            return  0;
        }
        if(root.left ==null&&root.right ==null){
            return 1;
        }
        int size = Size2(root.left) + Size2(root.right);
        return size;
    }



    //题 4 ：获取k层节点的个数
public int Count(Treenode root ,int k){
        //k层节点的个数等于左子树k-1层节点的个数+右子树k-1层节点的个数
    if(root ==null){
        return 0;
    }
    if(k ==1){
        return 1;
    }



    int size = Count(root.left,k-1)+ Count(root.right,k-1);



        return size;

}
//题5 ，获取二叉树的高度





    //题六，判断二叉树中是否有value值,不只是判断还要返回节点
    public TreeNode contains(TreeNode root , int val){
        //采用前序遍历
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode b1 = contains(root.left);
        if(b1!=null){
            return b1;
        }
        TreeNode b2 = contains(root.right);
         if(b2!=null){
             return b2;
         }
        return null;
    }
  //题目 6：判断两个树是否相同

    public boolean judge(TreeNode a, TreeNode b){

        if(a == null &&b!=null ||a!=null &&b == null){
              //两者结构不同,
            return false   ;
        }
       if(a.val !=b.val){
           return false;
       }
       if((a == null && b==null) ||( a .val == b.val)){
            return  true;
       }
       return  judge(a.left,b.left)&&judge(a.right,b.right);
    }

//题目7：判断一个数树中是否有与另一个树相同的子树
    public boolean contains2(TreeNode root,TreeNode subroot){
        //目的，是找到某个节点，使其子树与指定的树相同
        //遍历二叉树与判断两个树是否相同的方法不能用一个方法表述
        //按照根左右的方式进行遍历
        if(root == null){
            return false;
        }
       boolean b1 = judge(root,subroot);
        if(b1 == true){
            return b1;
        }
        return contains2(root.left,subroot) || contains2(root.right,subroot);

    }

    public static void main(String[] args) {



    }
}
